#include <atomic>
#include <limits>
#include <vector>
#include <cassert>

// fixed length atomic bitset
template<int BSIZE>
class FixedAtomicBitset {
private:
    /*
    * A wrapper that allows us to construct a vector of atomic elements
    * https://stackoverflow.com/questions/13193484/how-to-declare-a-vector-of-atomic-in-c
    */
    template<typename T>
    struct atomwrapper {
        std::atomic<T> _a;
        atomwrapper():_a(0) {}
        atomwrapper(const std::atomic<T> &a):_a(a.load()) {}
        atomwrapper(const atomwrapper &other):_a(other._a.load()) {}
        atomwrapper &operator=(const atomwrapper &other) {_a.store(other._a.load());}
        std::atomic<T> & ref() {return _a;}
        const std::atomic<T> & ref() const {return _a;}
    };

public:
    bool blindset(int & idx) {
        for(int i = 0; i < BLOCK_NUM; i++) {
            uint64_t xx = data_[i].ref().load();
            uint64_t tmp = ~(data_[i].ref().load());
            int slot = __builtin_clzll(tmp);
            if(tmp != 0 && set(i * kBitsPerBlock + slot) == false) {
                idx = i * kBitsPerBlock + slot;
                return true;
            }
        }
        return false;
    }

    bool set(size_t idx) {
        assert(idx < BSIZE);
        uint64_t mask = kOne << bitOffset(idx);
        return data_[blockIndex(idx)].ref().fetch_or(mask) & mask;
    }

    void reset(size_t idx) {
        assert(idx < BSIZE);
        uint64_t mask = kOne << bitOffset(idx);
        data_[blockIndex(idx)].ref().fetch_and(~mask) & mask;
    }

    bool get(size_t idx) const {
        uint64_t mask = kOne << bitOffset(idx);
        return data_[blockIndex(idx)].ref().load() & mask;
    }

    constexpr size_t size() const {
        return BSIZE;
    }

private:
    static constexpr size_t kOne = 1;
    static constexpr size_t kBitsPerBlock = std::numeric_limits<uint64_t>::digits;
    static constexpr int BLOCK_NUM = (BSIZE + kBitsPerBlock - 1) / kBitsPerBlock;

    static constexpr size_t blockIndex(size_t bit) {
        return bit / kBitsPerBlock;
    }

    static constexpr size_t bitOffset(size_t bit) {
        return kBitsPerBlock - 1 - bit % kBitsPerBlock;
    }

    atomwrapper<uint64_t> data_[BLOCK_NUM]; // filled at instantiation time
};